\bigskip
\bigskip
{\magonebf 5.4 Parameterized Graphs (GRAPH)}

A parameterized graph $G$ is a graph whose nodes and edges contain additional
(user defined) informations. Every node contains an element of a data type 
$vtype$, called the node type of $G$ and every edge contains an element of a 
data type $etype$ called the edge type of $G$. We use $<v,w,y>$ to denote an edge $(v,w)$ with information $y$ and $<x>$ to denote a node with information $x$.

All operations defined on instances of the data type $graph$ are also defined on
instances of any parameterized graph type $GRAPH(vtype,etype)$. For 
parameterized graphs there are additional operations to access or update the 
informations associated with its nodes and edges.  
Instances of a parameterized graph type can be used wherever an instance 
of the data type $graph$ can be used, e.g., in assignments and as 
arguments to functions with formal parameters of type $graph$ or $graph\&$. 
If a function $f(graph\&\ G)$ is called with an argument $Q$ of type 
$GRAPH(vtype,etype)$ then inside $f$ only the basic graph structure of $Q$ (the
adjacency lists) can be accessed. The node and edge informations are hidden.
This allows the design of generic graph algorithms, i.e., algorithms accepting
instances of any parametrized graph type as argument.


\bigskip
{\bf 1. Declaration of a parameterized graph type}


\decltwo GRAPH vtype etype

introduces a new data type with name \name\ consisting of all 
parameterized graphs with node type $vtype$ and edge type $etype$. 



\bigskip
{\bf 2. Creation of a parameterized graph}


\create G {}

creates an instance \var\ of type \name\ and initializes it to the
empty graph.


\bigskip
{\bf 3. \operations}

In addition to the operations of the data type $graph$ (see section 2):
\medskip
\+\op vtype  inf {node\ v}         
                          {returns the information of node $v$ } 
\medskip
\+\op etype  inf {edge\ e}         
                          {returns the information of edge $e$ }
\medskip
\+\op void   assign {node\ v,\ vtype\ x}
                          {makes $x$ the information of node $v$ }
\medskip
\+\op void   assign {edge\ e,\ etype\ y}
                          {makes $y$ the information of edge $e$ }
\medskip
\+\op node   new\_node {vtype\ x}   
                          {adds a new node $<x>$ to $G$ and returns it}
\medskip
\+\op edge   new\_edge {node\ v,\ w,\ etype\ x} {}
\+\nop                    {adds a new edge $e = <v,w,x>$ to $G$ by}
\+\nop                    {appending it to the adjacency list of $v$}
\+\nop                    { and returns $e$.}
\medskip
\+\op edge   new\_edge {edge\ e,\ node\  w,\ etype\ x,\ dir=after} {}
\+\nop                    {adds a new edge $e\' = <source(e),w,x>$ to $G$}
\+\nop                    {by inserting it after ($dir$=after) or before ($dir$}
\+\nop                    {=before) edge $e$ into the adjacency list of }
\+\nop                    {$source(e)$ and returns $e\'$.}
\medskip
\+\op void   sort\_nodes {}
                          {the nodes of $G$ are sorted according to their}
\+\nop                    {informations. \precond $vtype$ is linearly}
\+\nop                    {ordered.}
\smallskip
\+\op void   sort\_edges {}
                          {the edges of $G$ are sorted according to their}
\+\nop                    {informations. \precond $etype$ is linearly}
\+\nop                    {ordered.}
\smallskip
\+\op void   write {string\ fname}        
                          {writes $G$ to the file with name $fname$. The}
\+\nop                    {output functions $Print(vtype,ostream)$ and}
\+\nop                    {$Print(etype,ostream)$ (cf. section 1.6) must}
\+\nop                    {be defined. }
\smallskip
\+\op int   read {string\ fname}         
                          {reads $G$ from the file with name $fname$. The}
\+\nop                    {input functions $Read(vtype,istream)$ and }
\+\nop                    {$Read(etype,istream)$ (cf. section 1.6) must}
\+\nop                    {be defined. Returns error code}
\+\nop                    {1 \quad if file $fname$ does not exist}
\+\nop                    {2 \quad if graph is not of type $GRAPH(vtype,etype)$}
\+\nop                    {3 \quad if file $fname$ does not contain a graph}
\+\nop                    {0 \quad otherwise.}



\bigskip
{\bf 4. Operators}
\bigskip
\+\opa vtype\&  {node\ v}  
                           {returns a reference to $G$.inf($v$).}
\medskip
\+\opa etype\&  {edge\ e}  
                           {returns a reference to $G$.inf($e$).}

\bigskip
{\bf 5. Implementation}

Parameterized graphs are derived from directed graphs. All additional 
operations for manipulating the node and edge informations take constant
time.

\vfill\eject

